{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Common Prefix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #trie #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字典树 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestCommonPrefix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长公共前缀"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>编写一个函数来查找字符串数组中的最长公共前缀。</p>\n",
    "\n",
    "<p>如果不存在公共前缀，返回空字符串&nbsp;<code>\"\"</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>strs = [\"flower\",\"flow\",\"flight\"]\n",
    "<strong>输出：</strong>\"fl\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>strs = [\"dog\",\"racecar\",\"car\"]\n",
    "<strong>输出：</strong>\"\"\n",
    "<strong>解释：</strong>输入不存在公共前缀。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= strs.length &lt;= 200</code></li>\n",
    "\t<li><code>0 &lt;= strs[i].length &lt;= 200</code></li>\n",
    "\t<li><code>strs[i]</code> 仅由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-common-prefix](https://leetcode.cn/problems/longest-common-prefix/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-common-prefix](https://leetcode.cn/problems/longest-common-prefix/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"flower\",\"flow\",\"flight\"]', '[\"dog\",\"racecar\",\"car\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs: List[str]) -> str:\n",
    "        def FindPrefix(str1:str, str2:str) -> str:\n",
    "            i = 0\n",
    "            while(i<len(str1) and i<len(str2) and str1[i]==str2[i]):\n",
    "                i += 1\n",
    "            if i == 0:\n",
    "                return \"\"\n",
    "            else:\n",
    "                return str1[0:i]\n",
    "        \n",
    "        s = \"\"\n",
    "        if len(strs) == 0:\n",
    "            return \"\"\n",
    "        elif len(strs) == 1:\n",
    "            return strs[0]\n",
    "        else:\n",
    "            str0, str1 = strs[0], strs[1]\n",
    "            s = FindPrefix(str0, str1)\n",
    "            if s == \"\":\n",
    "                return \"\"\n",
    "            for i in range(2, len(strs)):\n",
    "                s = FindPrefix(s, strs[i])\n",
    "                if s == \"\":\n",
    "                    return s\n",
    "        return s\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs):\n",
    "        \"\"\"\n",
    "        :type strs: List[str]\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        ret = \"\"\n",
    "        if len(strs) == 0:\n",
    "            return ret\n",
    "\n",
    "\n",
    "        min_length = min([len(i) for i in strs])\n",
    "        \n",
    "        if min_length > 0:\n",
    "            for i in range(min_length + 1):\n",
    "                ret = str(strs[0][0:i])\n",
    "                if not all([j[0:i]==ret for j in strs]):\n",
    "                    if i > 0:\n",
    "                        ret = ret[0:-1]\n",
    "                        break\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs):\n",
    "        \"\"\"\n",
    "        :type strs: List[str]\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        result = ''\n",
    "        for x in zip(*strs):\n",
    "            if len(set(x))==1:\n",
    "                result +=list(set(x))[0]\n",
    "            else:\n",
    "                break\n",
    "        return result\n",
    "\n",
    "        # result = ''\n",
    "        # for x in zip(*strs):\n",
    "        #     if len(set(x))==1:\n",
    "        #         result +=list(set(x))[0]\n",
    "        #     else:\n",
    "        #         return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs):\n",
    "        \"\"\"\n",
    "        :type strs: List[str]\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        gby_answer = ''\n",
    "        a = list(zip(*strs))\n",
    "        for i in range(len(a)):\n",
    "            a[i] = list(a[i])\n",
    "            if a[i].count(a[i][0]) != len(a[i]):\n",
    "                break\n",
    "            else:\n",
    "                gby_answer += a[i][0]\n",
    "        return gby_answer\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self,strs):\n",
    "        if strs is None or len(strs) == 0:\n",
    "            return \"\"\n",
    "        strs = set(strs)\n",
    "        if len(strs) == 1:\n",
    "            return strs.pop()\n",
    "        \n",
    "        longestPrefix = strs.pop()\n",
    "        for str in strs:\n",
    "            if str == \"\":\n",
    "                return \"\"\n",
    "            if len(longestPrefix) >= len(str):\n",
    "                longestPrefix = longestPrefix[:len(str)]\n",
    "            else:\n",
    "                longestPrefix = longestPrefix[:len(longestPrefix)]\n",
    "            if len(str) > len(longestPrefix):\n",
    "                str = str[:len(longestPrefix)]\n",
    "            for idx, char in enumerate(str):\n",
    "                if char != longestPrefix[idx]:\n",
    "                    longestPrefix = longestPrefix[:idx]\n",
    "                    break\n",
    "        return longestPrefix\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs: List[str]) -> str:\n",
    "        res=''\n",
    "        if strs==[]:\n",
    "            return res\n",
    "        min_len=min([len(st) for st in strs])\n",
    "        for j in range(min_len):\n",
    "            flag=False\n",
    "            for i in range(len(strs)):\n",
    "                if i==0:\n",
    "                    tmp=strs[i][j]\n",
    "                    flag=True\n",
    "                else:\n",
    "                    if tmp==strs[i][j]:\n",
    "                        flag=True\n",
    "                    else:\n",
    "                        return res\n",
    "            if flag==True:\n",
    "                res+=tmp\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs: List[str]) -> str:\n",
    "        num2 = ''\n",
    "        \n",
    "        if len(strs) == 1:\n",
    "            return strs[0]\n",
    "        if len(strs) ==0 or strs==['']:\n",
    "            return \"\"\n",
    "        \n",
    "        for index in range(len(strs[1]) if len(strs[0])>len(strs[1]) else len(strs[1])):\n",
    "            if strs[0][:index+1] == strs[1][:index+1]:\n",
    "                num2 = strs[0][:index+1]\n",
    "            else:\n",
    "                break\n",
    "        if num2 == '':\n",
    "            return num2\n",
    "        \n",
    "        for j in range(1,len(strs)):\n",
    "            num3 = ''\n",
    "            for index in range(len(num2)):\n",
    "                \n",
    "                if strs[j][:index+1] == num2[:index+1]:\n",
    "                    num3 = num2[:index+1]\n",
    "                else:\n",
    "                    num2 = num3\n",
    "                    break\n",
    "        \n",
    "        return num2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs):\n",
    "        \"\"\"\n",
    "        :type strs: List[str]\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if strs == None or strs == []:\n",
    "            return ''\n",
    "        for i in range(len(strs[0])):\n",
    "            s = strs[0][i]\n",
    "            for j in range(len(strs)):\n",
    "                print(j)\n",
    "                if i >= len(strs[j]):\n",
    "                    return strs[j][:i]\n",
    "                elif strs[j][i] != s:\n",
    "                    return strs[0][:i]\n",
    " \n",
    "        return strs[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs):\n",
    "        \"\"\"\n",
    "        :type strs: List[str]\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        prefix = ''\n",
    "        if(strs is None or len(strs) == 0):\n",
    "            return prefix\n",
    "        first_str = strs[0]\n",
    "        index = 0\n",
    "        first_len = len(first_str)\n",
    "        while(index < first_len):\n",
    "            char = first_str[index]\n",
    "            for str in strs:\n",
    "                if(index >= len(str) or str[index] != char):\n",
    "                    return prefix\n",
    "            prefix += char\n",
    "            index += 1\n",
    "        return prefix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs):\n",
    "        \"\"\"\n",
    "        :type strs: List[str]\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        d = {}\n",
    "        for e in strs:\n",
    "            index = 0\n",
    "            for c in e:\n",
    "                key = c + str(index)\n",
    "                d[key] = (d[key] + 1) if key in d else 1\n",
    "                index += 1\n",
    "        l = len(strs)\n",
    "        ret = \"\"\n",
    "        if strs:\n",
    "            index = 0\n",
    "            for x in strs[0]:\n",
    "                key = str(x) + str(index)\n",
    "                if d[key] == l:\n",
    "                    ret += x\n",
    "                else:\n",
    "                    break\n",
    "                index += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs):\n",
    "        \"\"\"\n",
    "        :type strs: List[str]\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if len(strs)==0:\n",
    "            return \"\"\n",
    "        if \"\" in strs:\n",
    "            return \"\"\n",
    "        a=[]\n",
    "        for i in strs:\n",
    "            m=[]\n",
    "            for j in range(1,len(i)+1):\n",
    "                m.append(i[:j:])\n",
    "                a.append(m)\n",
    "        b=[]\n",
    "        for l in a[0]:\n",
    "            num=0\n",
    "            for k in a:\n",
    "                if l in k:\n",
    "                    num+=1\n",
    "            if num==len(a):\n",
    "                b.append(l)\n",
    "        b.sort(key=lambda x:len(x),reverse=True)\n",
    "        if len(b)==0:\n",
    "            return \"\"\n",
    "        else:\n",
    "            return b[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs):\n",
    "        if len(strs) == 0:\n",
    "            return ''\n",
    "        if len(strs) == 1:\n",
    "            return strs[0]\n",
    "        count = []\n",
    "        for s in strs:\n",
    "            te = len(s)\n",
    "            count.append(te)\n",
    "        out = min(count)\n",
    "        if out == 0:\n",
    "            return ''\n",
    "\n",
    "        def cut(st, wei):\n",
    "            nst = []\n",
    "            for x in st:\n",
    "                nst.append(x)\n",
    "            for m in range(len(nst)):\n",
    "                nst[m] = nst[m][:wei]\n",
    "            return nst\n",
    "        ultimate = []\n",
    "        t = 1\n",
    "        while 1 <= t <= out:\n",
    "            temp = cut(strs, t)\n",
    "            ultimate.append(temp)\n",
    "            t += 1\n",
    "        ultimate = list(map(set, ultimate))\n",
    "        ultimate = list(map(list, ultimate))\n",
    "        \n",
    "        res = [1]\n",
    "        i = 1\n",
    "        while 1 <= i <= out:\n",
    "            if len(ultimate[i-1]) != 1:\n",
    "                res[0] = i - 1\n",
    "                break\n",
    "            i += 1\n",
    "        if res[0] == 0:\n",
    "            return ''\n",
    "        if i == out + 1:\n",
    "            return ultimate[-1][0]\n",
    "        return ultimate[res[0]-1][0]\n",
    "        \"\"\"\n",
    "        :type strs: List[str]\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs):\n",
    "        \"\"\"\n",
    "        :type strs: List[str]\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        l = len(strs)\n",
    "        restr = ''\n",
    "        if l>0:\n",
    "            lenstr=len(strs[0])\n",
    "        else:\n",
    "            lenstr=0\n",
    "        for i in range(l):\n",
    "            lenstr = min(lenstr,len(strs[i]))\n",
    "        for i in range(lenstr):\n",
    "            j=1\n",
    "            while j<l:\n",
    "                print(j)\n",
    "                if(strs[j][i]==strs[0][i]):\n",
    "                    j=j+1\n",
    "                else:\n",
    "                    break\n",
    "            if j==l:\n",
    "                restr = restr+strs[0][i]\n",
    "            else:\n",
    "                break\n",
    "        return restr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs):\n",
    "        \"\"\"\n",
    "        :type strs: List[str]\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if len(strs) == 0:\n",
    "            return \"\"\n",
    "        if len(strs) == 1:\n",
    "            return strs[0]\n",
    "        length = []\n",
    "        dict_strs = []\n",
    "        nums = len(strs)\n",
    "        for i in range(nums):\n",
    "            length.append(len(strs[i]))\n",
    "            arr = [i for i in range(length[i])]\n",
    "            dict_strs.append(dict(zip(arr, strs[i])))\n",
    "        temp = 0\n",
    "        for j in range(min(length)):\n",
    "            for i in range(nums):\n",
    "                if temp != dict_strs[i][j] and temp != 0:\n",
    "                    if j == 0:\n",
    "                        return \"\"\n",
    "                    else:\n",
    "                        return strs[0][:j]\n",
    "                temp = dict_strs[i][j]\n",
    "            temp = 0\n",
    "        return strs[length.index(min(length))]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs: 'List[str]') -> 'str':\n",
    "        if strs==[]:\n",
    "            return''\n",
    "        if len(strs)==1:\n",
    "            return strs[0]\n",
    "        strs.sort()\n",
    "        p=''\n",
    "        for x,y in zip(strs[0],strs[-1]):\n",
    "            if x==y:\n",
    "                p+=x\n",
    "            else:\n",
    "                break\n",
    "        return p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs):\n",
    "        if len(strs) == 0 :\n",
    "            return \"\"\n",
    "        s1 = min(strs)\n",
    "        s2 = max(strs)\n",
    "        for i, x in enumerate(s1):\n",
    "            if x != s2[i]:\n",
    "                return s2[:i]\n",
    "        return s1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs: List[str]) -> str:\n",
    "        return os.path.commonprefix(strs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs: List[str]) -> str:\n",
    "        if len(strs) == 0:\n",
    "            return \"\"\n",
    "        all_len = len(strs)\n",
    "        min_len = len(strs[0])\n",
    "        word = strs[0]\n",
    "        flag = 1\n",
    "        for i in range(0, all_len):\n",
    "            if len(strs[i]) < min_len:\n",
    "                min_len = len(strs[i])\n",
    "                word = strs[i]\n",
    "        letter = [[] for i in range(min_len)]\n",
    "        for i in range(0, min_len):\n",
    "            for j in range(0, all_len):\n",
    "                letter[i].append(strs[j][i])\n",
    "        letter.append(['a','b','c'])\n",
    "        for i in range(len(letter)):\n",
    "            if len(set(letter[i])) != 1:\n",
    "                if i == 0:\n",
    "                    return \"\"\n",
    "                else:\n",
    "                    flag = i\n",
    "                    return word[:flag]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs: List[str]) -> str:\n",
    "        if not strs:\n",
    "            return ''\n",
    "        n = max([len(i) for i in strs])\n",
    "        ans=''\n",
    "        for i in range(n):\n",
    "            if len(strs[0]) <= i:\n",
    "                return ans\n",
    "            index = strs[0][i]\n",
    "            for word in strs:\n",
    "                if len(word)<=i or word[i] != index:\n",
    "                    return ans\n",
    "            ans += index\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs: List[str]) -> str:\n",
    "        sss = \"\"\n",
    "        sign = True\n",
    "        word_len = 0\n",
    "        if len(strs) > 0:\n",
    "            strs_len = [len(word) for word in strs]\n",
    "            min_word = strs[strs_len.index(min(strs_len))]\n",
    "            for i, s in enumerate(min_word):\n",
    "                for word in strs:\n",
    "                    if s != word[i]:\n",
    "                        sign = False\n",
    "                if sign:\n",
    "                    sss += s\n",
    "            return sss\n",
    "        else:\n",
    "            return sss\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs: List[str]) -> str:\n",
    "        if not strs: return ''\n",
    "        s0 = min(strs)\n",
    "        s1 = max(strs)\n",
    "        for i in range(len(s0)):\n",
    "            if s0[i] != s1[i]:\n",
    "                return s0[:i]\n",
    "        return s0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs: List[str]) -> str:\n",
    "        if len(strs) == 0 or len(strs) == 1:\n",
    "            return (\"\".join(strs))\n",
    "        List = []\n",
    "        ShortestStr = min(strs, key = len)\n",
    "        Shortest = len(ShortestStr)\n",
    "        if Shortest == 0:\n",
    "            return (\"\")\n",
    "\n",
    "        for i in range(Shortest):\n",
    "            for j in range(len(strs)):\n",
    "                if strs[j][i] != ShortestStr[i]:\n",
    "                    return (\"\".join(List))\n",
    "                elif j == len(strs) - 1:\n",
    "                    List.append(ShortestStr[i])\n",
    "        return (\"\".join(List))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs: List[str]) -> str:\n",
    "        if not strs: return ''\n",
    "        str_min = min(strs)\n",
    "        str_max = max(strs)\n",
    "        for i in range(len(str_min)):\n",
    "            if str_min[i] != str_max[i]:\n",
    "                return str_min[:i]\n",
    "        return str_min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs: List[str]) -> str:\n",
    "        if strs == []:return \"\"\n",
    "        st = strs[0]\n",
    "        same = True\n",
    "        j=0\n",
    "        while True:\n",
    "            for i in range(len(strs)):\n",
    "                print(len(strs[i]))\n",
    "                if j==min(len(strs[i]),len(st)) or strs[i][j] != st[j]:\n",
    "                    s = \"\" if j==0 else st[:j]\n",
    "                    return s\n",
    "            j+=1\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs: List[str]) -> str:\n",
    "        if not strs:\n",
    "            return \"\"\n",
    "        if strs[0] == \"\":\n",
    "            return \"\"\n",
    "        \n",
    "        pre = strs[0][0:1]\n",
    "        for s in strs:\n",
    "            if s[0:1] != pre:\n",
    "                return \"\"\n",
    "        else:\n",
    "            return pre + self.longestCommonPrefix([s[1:] for s in strs])\n",
    "        \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs: List[str]) -> str:\n",
    "        temp = []\n",
    "        for i in strs:\n",
    "            temp.append(list(i))\n",
    "    \n",
    "        temp_1 = []\n",
    "        for l in temp:\n",
    "            for idx, v in enumerate(l):\n",
    "                temp_1.append((idx,v))\n",
    "\n",
    "        b = Counter(temp_1)\n",
    "\n",
    "        ans = []\n",
    "        for k in b.keys():\n",
    "            if b[k] == len(strs) and [i for i in range(k[0])] == ans[:k[0]]:\n",
    "                ans.append(k[0])\n",
    "    \n",
    "        answer = ''\n",
    "        for i in ans:\n",
    "            answer += strs[0][i]\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs: List[str]) -> str:\n",
    "        if len(strs) == 0:\n",
    "            return ''\n",
    "        prefix = strs[0]\n",
    "        for i in range(1, len(strs)):\n",
    "            prefix = self.lcp(prefix, strs[i])\n",
    "        return prefix\n",
    "        \n",
    "    def lcp(self, str1, str2):\n",
    "        count, index = min(len(str1), len(str2)), 0\n",
    "        while index < count and str1[index] == str2[index]:\n",
    "            index += 1\n",
    "        return str1[:index]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs: List[str]) -> str:\n",
    "        minlen = min([len(i) for i in strs])\n",
    "        print(minlen)\n",
    "        if minlen == 0:\n",
    "            return \"\"\n",
    "        else:\n",
    "            if minlen == 1:\n",
    "                list2 = list(set([i[0] for i in strs]))\n",
    "                if len(list2) == 1:\n",
    "                    return strs[0][0]\n",
    "                else:\n",
    "                    return \"\"\n",
    "            else:\n",
    "                index1 = 0       \n",
    "                list2 = list(set([i[index1] for i in strs]))\n",
    "                if len(list2) == 1:            \n",
    "                    while index1 < minlen-1 and len(list2) == 1:\n",
    "                        index1 += 1                    \n",
    "                        list2 = list(set([i[index1] for i in strs]))\n",
    "                    if len(list2) == 1:\n",
    "                        index1 += 1 \n",
    "                    return strs[0][:index1]\n",
    "                else:\n",
    "                    return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs: List[str]) -> str:\n",
    "        length = len(strs)\n",
    "        if length == 1:\n",
    "            return strs[0]\n",
    "        long_str = max(strs)\n",
    "        short_str = min(strs)\n",
    "        for i in range(len(short_str)):\n",
    "            if short_str[i] != long_str[i]:\n",
    "                return short_str[:i]\n",
    "        return short_str"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def longestCommonPrefix(self, strs: List[str]) -> str:\r\n",
    "        if len(strs) == 1:\r\n",
    "            return strs[0]\r\n",
    "        m = min(strs, key=len)\r\n",
    "        if m == \"\":\r\n",
    "            return \"\"\r\n",
    "        for i in range(0, len(m)):\r\n",
    "            for j in strs:\r\n",
    "                if i == len(j) or m[i] != j[i]:\r\n",
    "                    return m[:i]\r\n",
    "        return m\r\n",
    "                  \r\n",
    "                \r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs: List[str]) -> str:\n",
    "        s = strs[0]\n",
    "        j = 0\n",
    "        ans = ''\n",
    "        for i in range(len(s)):\n",
    "            \n",
    "            for j in range(1,len(strs)):\n",
    "                print(len(strs[j]))\n",
    "                print(i)\n",
    "                if len(strs[j]) > i and s[i] == strs[j][i]:\n",
    "                    continue\n",
    "                else:\n",
    "                    return ans\n",
    "            ans += s[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs: List[str]) -> str:\n",
    "\n",
    "        \n",
    "        keycount=0\n",
    "        \n",
    "        # equlList=[]\n",
    "        for chip in range(200+1):\n",
    "            equlList=[]\n",
    "            count=1\n",
    "            for word in strs:\n",
    "                \n",
    "                # print(len(word))\n",
    "                print(chip)\n",
    "                if len(word)>0:\n",
    "                    # print(chip)\n",
    "                    if chip<=len(word):\n",
    "                        equlList.append(word[:chip+1])\n",
    "\n",
    "                else:\n",
    "                    return ''\n",
    "\n",
    "            print(equlList)\n",
    "            if len(equlList)>1:\n",
    "                for i in range(len(equlList)-1):\n",
    "                    if equlList[0]==equlList[i+1]:\n",
    "                        count+=1\n",
    "\n",
    "                    else:\n",
    "                        break\n",
    "\n",
    "                print(count)\n",
    "\n",
    "                if count==len(strs):\n",
    "                    iseuql=True\n",
    "\n",
    "                else:\n",
    "                    iseuql=False\n",
    "                \n",
    "                if (iseuql):\n",
    "                    keycount+=1\n",
    "                    continue\n",
    "                else:\n",
    "                    if keycount>=1:\n",
    "                        return strs[0][0:chip]\n",
    "                    else:\n",
    "                        return ''\n",
    "\n",
    "            # elif len(equlList)==1:\n",
    "            #     if equlList[0]==equlList[1]:\n",
    "            \n",
    "            \n",
    "            else:\n",
    "                \n",
    "                return strs[0]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs: List[str]) -> str:\n",
    "        res = ''\n",
    "        for i in zip(*strs):\n",
    "            if len(set(i)) == 1:\n",
    "                res += i[0]\n",
    "            else:\n",
    "                break\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs: List[str]) -> str:\n",
    "        a=min(list(map(len,strs))) #最长共同长度\n",
    "        b=len(strs) #元素个数\n",
    "        data = ''  # 用于存储没有对比失败的情况下的 i 值\n",
    "\n",
    "        for i in range(a):\n",
    "            for j in range(1, b):\n",
    "                if strs[j][i] != strs[0][i]:\n",
    "                    return data\n",
    "                    quit()\n",
    "            else:\n",
    "                data+=strs[0][i]\n",
    "        return data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs: List[str]) -> str:\n",
    "\n",
    "        # image them like a table\n",
    "\n",
    "        if not strs:\n",
    "            return \"\"\n",
    "\n",
    "        count = len(strs)\n",
    "\n",
    "        first_s = strs[0]\n",
    "\n",
    "        for i in range(len(first_s)):\n",
    "            c = strs[0][i]\n",
    "\n",
    "            for j in range(1, count):\n",
    "                if i == len(strs[j]):\n",
    "                    return strs[0][:i]\n",
    "\n",
    "                if strs[j][i] != c:\n",
    "                    return strs[0][:i]\n",
    "                    \n",
    "\n",
    "        return strs[0]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
